#include <iostream>
#include <vector>

using namespace std;

// 100.00 %
class Solution1 {
private:
	vector<int> memo;
	int calWays(int n) {
		if( n == 0 || n == 1 ) return 1;
        if ( memo[n] == -1 )
			memo[n] = calWays( n-1 ) +  calWays(n-2);
		return memo[n];
	}
public:
    int climbStairs(int n) {
		memo = vector<int>( n+1, -1);
		return calWays(n);
    }
};

// 100.00 %
class Solution {
public:
    int climbStairs(int n) {
        vector<int> memo( n+1, -1);
		memo[0] = memo[1] = 1;
		for( int i=2; i <=n; i++ ) {
			memo[i] = memo[i-1] + memo[i-2];
		}
		return memo[n];
    }
};

int main() {
    int n = 35;
    cout << Solution().climbStairs(n) << endl;
    return 0;
}
